class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]
'''
最简单就是排序返回中位数
要么就是记一个count = val +1 else -1 + count == 0 res = i
1. 使用defaultdict完成取字典value的最大值
2. 从而简化了判空以及通过keys+key: lambda取value最大的key的操作
3. 还可以用collection的counter
'''
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dict = defaultdict(int)
        for i in nums:
            dict[i] += 1
        return max(dict.keys(), key=lambda x: dict[x])

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

'''
摩尔投票法
核心就是数值相等的时候+1 否则-1 但是因为众数超过一半所以无论如何, 最后的哪个0对应的num就是众数
'''
class Solution:
    def majorityElement(self, nums):
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate
'''
不能放进else里面因为=0是上一次的所以这次还是需要+1/-1
'''
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        res = None
        count = 0
        for i in nums:
            if count == 0:
                res = i
            count += ( 1 if i == res else -1)
        return res